\documentclass[a4paper,11pt]{article}

\usepackage[spanish, activeacute]{babel}
\usepackage{caratula}
\usepackage{amsfonts}
\usepackage{color}
\usepackage{graphicx}
\usepackage{float}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{fontenc}
\usepackage{listings}
\usepackage{amssymb}
\usepackage{slashbox}
\usepackage{url} 
\usepackage{epsf}
\usepackage[margin=2cm]{geometry}
\usepackage[bookmarks=true]{hyperref}


\oddsidemargin  -0.0in
\evensidemargin -0.0in
\textwidth      6.3in
\headheight     0.0in
\topmargin      -0.4in
\textheight		9.5in

\begin{document}

\input{caratula}


\tableofcontents

\newpage



\section{Modificaciones a la gr\'amatica}

\begin{tabular}{lcll}
E & $\rightarrow$ & E E & (concatenaci\'on)\\
  & $|$ & E $\hat{}$ E & (super\'indice)\\
  & $|$ & E $\_$ E & (sub\'indice)\\
  & $|$ & E $\hat{}$ E $\_$ E & (super y sub\'indice)\\
  & $|$ & E $\_$ E $\hat{}$ E & (sub y super\'indice)\\
  & $|$ & E $/$ E & (divisi\'on)\\
  & $|$ & ( E ) & (encerrar entre par\'entesis)\\
  & $|$ & \{ E \} & (agrupar)\\
  & $|$ & l & (cualquier caracter salvo $\hat{}$, $\_$, $/$, \{, \}, ( y ))
\end{tabular}

\bigskip

En primer lugar se tiene una gr\'amatica que describe correctamente el lenguaje que se quiere generar, pero lo hace abusando de la idea de que una subexpresi\'on siempre puede ser modelada como una expresi\'on por si sola. De esta forma, la gram\'atica presentada resulta ambigua, y no preserva la asociatividad ni la precendencia requerida para este lenguaje.

Es por lo dicho anteriormente que se procedi\'o a modificar la gram\'atica para que, en primer lugar, cumpla con las precendencias y las asociatividades dispuestas, adem\'as de perder la ambiguedad.

\bigskip

\subsection{Modificaciones iniciales}

A continuaci\'on se presenta una primer modificaci\'on de la gr\'atica en la cual ya se resolvieron dos problemas. Por un lado, ya se encuentra resuelto el problema de la precedencia, esto se hizo de la misma manera que se realiz\'o durante el transcurso de la materia; es decir, posicionando los operadores de menor precendencia m\'as cercanos al simbolo inicial de la gram\'atica.

Por otro lado, se resolvio el problema de la asociatividad para la divisi\'on y para la concatenaci\'on. Para lograr que estas dos operaciones sean asociativas a izquierda, la recursi\'on para generar estas construcciones se puso a la izquierda tambi\'en logrando lo requerido.

La primera modificaci\'on de la gram\'atica qued\'o entonces:

\bigskip

\begin{tabular}{lcl}
E & $\rightarrow$ & E $/$ F $|$ F\\
F & $\rightarrow$ & F G $|$ G\\
G & $\rightarrow$ & T $\hat{}$ T $|$ T $\_$ T $|$ T\\
T & $\rightarrow$ & (E) $|$ \{E\} $|$ T $\hat{}$ T $\_$ T $|$ T $\_$ T $\hat{}$ T $|$ C\\
C & $\rightarrow$ & CARACTER
\end{tabular}



\subsection{Modificaciones para la implementaci\'on}

Si bien la anterior modificaci\'on sirve para resolver algunos problemas, la gram\'atica presentada todav\'ia tiene algunos otros. Por ejemplo, es incapaz de generar un archivo postscript en el cual los caracteres esten bien ubicados dadas las especificaciones del enunciado. Para poder implementar el generador del postscript fue necesario adherirle atributos a los simbolos de la gram\'atica que indicasen varias caracter\'isticas importantes como la posici\'on y el tama\~{n}o entre otras.

Para realizar esto, se cuenta con una estructura de atributos, la cual se encuentra definida en el archivo tp.h

A continuaci\'on, se presentan dichos atributos

\lstset{language=C}
\newpage
\begin{lstlisting}
typedef struct tagStruct {
    float x, y, escala;
    float ancho, h1, h2;
    int tipo;
    char caracter;
    int * hijo1;
    int * hijo2;
    int * hijo3;
} nodeType;
\end{lstlisting}

\medskip

\begin{itemize}
\item En los floats x e y se guardan las coordenadas de lo que se quiere escribir.
\item En el float escala se guarda el tama\~{n}o con respecto del tama\~{n}o inicial.
\item Los floats ancho, h1 y h2 se utilizan para las dimensiones del caracter.
\item Luego, se guarda el tipo del nodo y el caracter que representa.
\item Los punteros a hijos son 3 dado que la mayor producci\'on presente en la gram\'atica tiene 3 simbolos no terminales del lado derecho.
\end{itemize}

Con esta estructura se logr\'o obtener la informaci'on necesaria para lograr el postscript requerido. Se explicar\'a m\'as en detalle como fue realizado esto en la secci\'on 2.2.



\subsection{Indicaciones adicionales}

Una vez adheridos los atributos mencionados anteriormente, se tuvieron las herramientas necesarias para generar el postscript final. Sin embargo, la gram\'atica todav\'ia preserva un problema sin solucionar; los operadores para sub\'indices y super\'indices no deben ser asociativos y, si se deja la gram\'atica tal cual est\'a, lo son.

La soluci\'on para el problema de la no asociatividad de los super\'indices y los sub\'indices fue utilizar un flag en el yacc que le indica al generador del parser que estos simbolos no son asociativos.

Para realizar esto se agreg\'o la siguiente linea el archivo de entrada del yacc (tp.y):
\begin{lstlisting}
%nonassoc '_' '^'
\end{lstlisting}

De esta manera, se pudo solucionar dicho problema.

\newpage
\section{Descripci\'on de la implementaci\'on}

A continuaci\'on se describir\'an los diferentes pasos realizados para la implementaci\'on del presenta trabajo.

\subsection{Lex}

La implementaci\'on realizada para lex fue bastante sencilla dado que la generaci\'on de los tokens lo era. Lo \'unico que se hizo fue proveer al lex de tres reglas b\'asicas:

\begin{itemize}
\item Una primera regla para reconocer el \emph{enter} en la consola. Es decir, se toma el enter en la cadena de entrada como el simbolo $\$$ utilizado habitualmente.
\item Una segunda regla comod\'in que reconoce cualquier otro caracter diferente a los reservados, que en nuestro caso van a ser las letras utilizadas para las expresiones.
\item Una tercera regla para reconocer todos los caracteres importantes que forman parte de la gram\'atica.
\end{itemize}


Toda esta informaci\'on, m\'as la inclusi\'on de algunos headers necesarios, se encuentra en el archivo \emph{tp.l} que es el archivo de entrada de lex. Al correr el lex con dicho archivo se genera el archivo \emph{lex.yy.c} con todo el c\'odigo generado.

\subsection{Yacc}

La implementaci\'on realizada para el yacc fue la m\'as importante en este trabajo. En primer lugar, se encuentran definidas varias declaraciones necesarias para el objetivo a realizar. Luego de estas definiciones se encuentra la definici\'on de la gram\'atica presentada en la secci\'on 1.1 con todas sus producciones, dentro de cada una de ellas se encuentra el c\'odigo necesario para crear una estructura propia que representa el arbol de parseo sobre el cual se calculan los atributos.

Una vez finalizadas las producciones de la gram\'atica, se encuentran las funciones pertinentes al manejo de los atributos. La idea es tener una funci\'on general, llamada \emph{analizar\_grafo} que se encargue, justamente, de recorrer todo el arbol de parsing e ir actuando pertinentemente. En realidad, las funci\'ones de analizar\_grafo son las siguientes:

\begin{enumerate}
\item Verificar que la raiz del arbol, realmente es de tipo raiz y no hubo ning\'un problema en la generaci\'on.
\item Crear el archivo postscript de salida.
\item Setear algunos atributos iniciales.
\item Llamar al m\'etodo propagar\_escala.
\item Generar las primeras lineas del archivo de salida que son comunes a todos los caracteres del archivo.
\item Llamar al m\'etodo propagar\_heredados.
\item Liberar la memoria pedida y cerrar el archivo de salida.
\end{enumerate}

Para entender bien el funcionamiento total de la implementaci\'on hace falta explicar que hacen los m\'etodos propagar\_escala y propagar\_heredados.


\bigskip

Propagar\_escala:

La funci\'on propagar escala hace justamente lo que dice su nombre, sintetizando otros atributos necesarios en el camino. Su funcionamiento es bastante simple, se trata de un switch respecto del tipo de nodo que se esta analizando, y en base a esto se hacen los c\'alculos necesarios dependiendo el caso en el que se este.

\medskip

Propagar\_heredados:

Esta funci\'on actua de forma parecida al anterior, es un switch que depende del tipo de nodo que se este analizando. La diferencia importante es que esta funci\'on va propagando todos los atributos heredados de la gr\'amatica con los cuales ya es posible generar el c\'odigo de salida. Es por esto, que dentro de cada caso del switch, la funci\'on propagar\_heredados va generando el c\'odigo necesario en el postscript de salida.

\bigskip

Todos los m\'etodos y la gram\'atica descripta se encuentra en el archivo \emph{tp.y} que es el archivo de entrada para el yacc. Al correr el yacc con este archivo de entrada se generan tres archivos de salida.

\begin{itemize}
\item tp.cc: Es el c\'odigo generado por yacc.
\item tp.hh: Son deficiones y declaraciones de tipos que fueron declarados en tp.y.
\item tp.output: Es un archivo opcional generado por yacc con la descripci\'on del parser. Contiene un resumen de las producciones, los estados del aut\'omata utilizado para generar el parser y una secci\'on estad\'isticas del parser generado.
\end{itemize}



\subsection{Implementaci\'on final}

Luego de utilizar el lex y el yacc se procede con dos pasos m\'as para la finalizaci\'on del trabajo.

\bigskip

En primer lugar, se compila el c\'odigo generado por el lex mediante el comando

cc -g -c lex.yy.c -o lex.yy.o

\bigskip

Por \'ultimo se compila todo lo obtenido mediante el comando

c++ -g lex.yy.o tp.cc -o tp.exe


Generando asi el programa final para ser utilizado.

\bigskip

Para realizar todos los pasos mencionados anteriormente se entrega un makefile junto con el c\'odigo del trabajo.


\newpage
\section{Ejemplos}


En esta secci\'on se presentan los test de las f\'ormulas que estan correctamente generadas y que, por lo tanto, tienen que ser bien parseadas por la implementaci\'on. Cabe destacar que tambi\'en se hicieron tests para f\'ormulas que no se encontraban bien generadas, como por ejemplo tratar de asociar sub\'indices o super\'indices, en todos esos casos la implementaci\'on no gener\'o un postscript sino que avis\'o por consola que la f\'ormula era invalida.

Todas los archivos generados en los casos de tests se encuentran en la carpeta Tests.

\bigskip

\noindent Caso 1:

\noindent Testeo simple de la suma. F\'ormula: A+B.

\medskip

\noindent \%!PS-Adobe-3.0 EPSF-3.0 \\
\%\%BoundingBox: 0 0 27 33 \\
2 4 translate \\
12 12 scale \\
.03 setlinewidth \\
/Courier findfont setfont\\ 
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0 moveto 1 1 scale (+) show grestore\\
gsave 1.2 0 moveto 1 1 scale (B) show grestore\\

\bigskip


\noindent Caso 2:

\noindent Testeo simple de la divisi\'on. F\'ormula: A$/$B

\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 15 33\\
2 11 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0.48 moveto 1 1 scale (A) show grestore\\
gsave 0 -0.62 moveto 1 1 scale (B) show grestore\\
gsave 0 0.28 moveto 0.6 0 rlineto stroke grestore\\


\bigskip

\noindent Caso 3:

\noindent Testeo simple de super\'indice. F\'ormula: A$\hat{}$B

\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 4 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0.45 moveto 0.7 0.7 scale (B) show grestore\\

\bigskip

\noindent Caso 4:

\noindent Testeo simple de sub\'indice. F\'ormula: A$\_$B

\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 6 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 -0.22 moveto 0.7 0.7 scale (B) show grestore\\

\bigskip

\noindent Caso 5:

\noindent Testeo simple de super y sub\'indice. F\'ormula: A$\hat{}$B$\_$C

\medskip
\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 6 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0.45 moveto 0.7 0.7 scale (B) show grestore\\
gsave 0.6 -0.22 moveto 0.7 0.7 scale (C) show grestore\\
\bigskip

\noindent Caso 6:

\noindent Testeo simple de sub y super\'indice. F\'ormula: A$\_$B$\hat{}$C

\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 6 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 -0.22 moveto 0.7 0.7 scale (B) show grestore\\
gsave 0.6 0.45 moveto 0.7 0.7 scale (C) show grestore\\

\bigskip

\noindent Caso 7:

\noindent Testeo para la precedencia entre la concatenaci\'on y la divisi\'on. F\'ormula: A+B$/$C
% "A+B/C"
\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 11 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0.48 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0.48 moveto 1 1 scale (+) show grestore\\
gsave 1.2 0.48 moveto 1 1 scale (B) show grestore\\
gsave 0.6 -0.62 moveto 1 1 scale (C) show grestore\\
gsave 0 0.28 moveto 1.8 0 rlineto stroke grestore\\

\bigskip

\noindent Caso 8:

\noindent Testeo para la precendencia entre los \'indices y la divisi\'on. F\'ormula: A$\hat{}$B$/$C$\_$D
% "A^B/C_D"
\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 14 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0.48 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0.93 moveto 0.7 0.7 scale (B) show grestore\\
gsave 0 -0.62 moveto 1 1 scale (C) show grestore\\
gsave 0.6 -0.85 moveto 0.7 0.7 scale (D) show grestore\\
gsave 0 0.28 moveto 1 0 rlineto stroke grestore\\

\bigskip

\noindent Caso 9:

\noindent Testeo para la precendencia entre los \'indices y la divisi\'on. F\'ormula: A$\hat{}$B$\_$C$/$D
% "A^B_C/D"
\medskip
\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 11 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0.7 moveto 1 1 scale (A) show grestore\\
gsave 0.6 1.2 moveto 0.7 0.7 scale (B) show grestore\\
gsave 0.6 0.48 moveto 0.7 0.7 scale (C) show grestore\\
gsave 0.21 -0.62 moveto 1 1 scale (D) show grestore\\
gsave 0 0.28 moveto 1 0 rlineto stroke grestore\\

\bigskip

\noindent Caso 10:

\noindent Testeo para varias precendencias. F\'ormula: A$\hat{}$B$\_$C$/$D+E
% "A^B_C/D+E"
\medskip
\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 11 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0.39 0.7 moveto 1 1 scale (A) show grestore\\
gsave 0.99 1.2 moveto 0.7 0.7 scale (B) show grestore\\
gsave 0.99 0.48 moveto 0.7 0.7 scale (C) show grestore\\
gsave 0 -0.62 moveto 1 1 scale (D) show grestore\\
gsave 0.6 -0.62 moveto 1 1 scale (+) show grestore\\
gsave 1.2 -0.62 moveto 1 1 scale (E) show grestore\\
gsave 0 0.28 moveto 1.8 0 rlineto stroke grestore\\
\bigskip

\noindent Caso 11:

\noindent Testeo para varias dependecias. F\'ormula: A$\hat{}$B$\_$C-G$/$D+E$\hat{}$F
% "A^B_C-G/D+E^F"
\medskip
\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 39 33\\
2 13 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0.7 moveto 1 1 scale (A) show grestore\\
gsave 0.6 1.2 moveto 0.7 0.7 scale (B) show grestore\\
gsave 0.6 0.48 moveto 0.7 0.7 scale (C) show grestore\\
gsave 1 0.7 moveto 1 1 scale (-) show grestore\\
gsave 1.6 0.7 moveto 1 1 scale (G) show grestore\\
gsave 0 -0.77 moveto 1 1 scale (D) show grestore\\
gsave 0.6 -0.77 moveto 1 1 scale (+) show grestore\\
gsave 1.2 -0.77 moveto 1 1 scale (E) show grestore\\
gsave 1.8 -0.32 moveto 0.7 0.7 scale (F) show grestore\\
gsave 0 0.28 moveto 2.2 0 rlineto stroke grestore\\

\bigskip

\noindent Caso 12:

\noindent Testeo de par\'entesis para sacar precendecia. F\'ormula: A$\hat{}$B$\_$C-G$/$(D+E)$\hat{}$F
% "A^B_C-G/(D+E)^F"
\medskip
\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 51 33\\
2 13 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0.6 0.7 moveto 1 1 scale (A) show grestore\\
gsave 1.2 1.2 moveto 0.7 0.7 scale (B) show grestore\\
gsave 1.2 0.48 moveto 0.7 0.7 scale (C) show grestore\\
gsave 1.6 0.7 moveto 1 1 scale (-) show grestore\\
gsave 2.2 0.7 moveto 1 1 scale (G) show grestore\\
gsave 0.6 -0.77 moveto 1 1 scale (D) show grestore\\
gsave 1.2 -0.77 moveto 1 1 scale (+) show grestore\\
gsave 1.8 -0.77 moveto 1 1 scale (E) show grestore\\
gsave 0 -0.77 moveto 1 1.5 scale ($\backslash$() show grestore\\
gsave 2.4 -0.77 moveto 1 1.5 scale ($\backslash$)) show grestore\\
gsave 3 -0.32 moveto 0.7 0.7 scale (F) show grestore\\
gsave 0 0.28 moveto 3.4 0 rlineto stroke grestore\\

\bigskip

\noindent Caso 13:

\noindent Testeo de agrupaciones para sacar precendecia. F\'ormula: A$\hat{}$B$\_$C-\{G$/$(D+E)$\hat{}$F\}
% "A^B_C-{G/(D+E)^F}"
\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 75 33\\
2 13 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0.45 moveto 0.7 0.7 scale (B) show grestore\\
gsave 0.6 -0.22 moveto 0.7 0.7 scale (C) show grestore\\
gsave 1 0 moveto 1 1 scale (-) show grestore\\
gsave 3 0.48 moveto 1 1 scale (G) show grestore\\
gsave 2.2 -0.77 moveto 1 1 scale (D) show grestore\\
gsave 2.8 -0.77 moveto 1 1 scale (+) show grestore\\
gsave 3.4 -0.77 moveto 1 1 scale (E) show grestore\\
gsave 1.6 -0.77 moveto 1 1.5 scale ($\backslash$() show grestore\\
gsave 4 -0.77 moveto 1 1.5 scale ($\backslash$)) show grestore\\
gsave 4.6 -0.32 moveto 0.7 0.7 scale (F) show grestore\\
gsave 1.6 0.28 moveto 3.4 0 rlineto stroke grestore\\

\bigskip

\noindent Caso 14:

\noindent Testeo para super\'indice compuesto. F\'ormula: A$\hat{}$\{B$\hat{}$C\}
% A^{B^C}
\medskip

\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 4 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0.45 moveto 0.7 0.7 scale (B) show grestore\\
gsave 1 0.76 moveto 0.49 0.49 scale (C) show grestore\\

\bigskip

\noindent Caso 15:
% A^{B^{C^D}}
\noindent Testeo para super\'indice compuesto. F\'ormula: A$\hat{}$\{B$\hat{}$\{C$\hat{}$D\}\}

\medskip
\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 4 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 0.45 moveto 0.7 0.7 scale (B) show grestore\\
gsave 1 0.76 moveto 0.49 0.49 scale (C) show grestore\\
gsave 1.3 0.99 moveto 0.34 0.34 scale (D) show grestore\\


\bigskip

\noindent Caso 16:

\noindent Testeo para sub\'indice compuesto. F\'ormula: A$\_$\{B$\_$C\}
% A_{B_C}
\medskip
\noindent\%!PS-Adobe-3.0 EPSF-3.0\\
\%\%BoundingBox: 0 0 27 33\\
2 8 translate\\
12 12 scale\\
.03 setlinewidth\\
/Courier findfont setfont\\
gsave 0 0 moveto 1 1 scale (A) show grestore\\
gsave 0.6 -0.22 moveto 0.7 0.7 scale (B) show grestore\\
gsave 1 -0.38 moveto 0.49 0.49 scale (C) show grestore\\



\end{document}
